package com.my.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Created by ZhongGang
 * at 2018/10/8 17:53
 * <p>
 * 希尔排序 插入排序的变种形式
 * 按升级排列的插入排序算法在输入数组是降序的情况下，每一次遍历排序都要经历N次比较，属于最坏情况
 * 希尔排序则是根据提供的间隔遍历数组，依次遍历
 * 比如希尔排序提供的间隔数组是[9, 3, 1]
 * 则每一次遍历使用间隔数组中的一个元素，来进行插入排序
 * 当间隔数组元素为1时，则是普通的插入排序
 * 通过间隔遍历的方式避免最坏情况下的全量比较
 */
public class ShellSorter<T extends Comparable<T>> implements Sortable<T> {
    private static final Logger LOGGER = LoggerFactory.getLogger(ShellSorter.class);

    @Override
    public T[] sort(T[] elements) {
        if (elements == null || elements.length < 2) {
            return elements;
        }

        int length = elements.length;
        int shell = length / 3;
        shell = shell == 0 ? 1 : shell;

        while (true) {

            for (int i = 0; i < shell; i++) {
                for (int j = i + shell; j < length; j += shell) {
                    for (int k = j; k > i; k -= shell) {
                        if (elements[k - shell].compareTo(elements[k]) > 0) {
                            T tmp = elements[k];
                            elements[k] = elements[k - shell];
                            elements[k - shell] = tmp;
                        }
                        LOGGER.info("shell: {}, i: {}, j: {}, k: {}, elements: {}", shell, i, j, k, elements);
                    }
                }
            }

            if (shell == 1) {
                break;
            }

            shell = shell / 3;
            shell = shell == 0 ? 1 : shell;
        }

        return elements;
    }
}
